BZOJ1070【SCOI2007】修车 <费用流>

Problem

【SCOI2007】修车

Description

同一时刻有位车主带着他们的爱车来到了汽车维修中心。维修中心共有位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个，表示技术人员数与顾客数。接下来行，每行个整数。第行第个数表示第位技术人
员维修第辆车需要用的时间。

Output

最小平均等待时间，答案精确到小数点后位。

Sample Input

1
2
3

2 2
3 2
1 4

Sample Output

1.50

HINT

数据范围: , ,

标签：费用流

Solution

此题建模是费用流中常见的拆点建模。
把每个技术人员拆成个点，第个点代表着此工作人员修的倒数第辆车对答案的贡献。
对于每个顾客，如果他倒数第个修车，花费的时间，会对答案产生的贡献。
因此从每个顾客向每个技术人员的个点连边，容量为，花费为，然后跑费用流即可。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 10000
#define MAX_M 200000
#define INF 2147483647
using namespace std;
int n, m, s, t, ans, a[65][10];
int pre[MAX_N+5], cnt;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n*m+n+1, cnt = 0;	memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c, int w) {
    E[cnt].v = v, E[cnt].c = c, E[cnt].w = w, E[cnt].nxt = pre[u], pre[u] = cnt++;
    E[cnt].v = u, E[cnt].c = 0, E[cnt].w =-w, E[cnt].nxt = pre[v], pre[v] = cnt++;
}
bool SPFA() {
    queue <int> que;	bool inque[MAX_N+5];	int dis[MAX_N+5], pree[MAX_N+5];
    memset(inque, false, sizeof(inque)), memset(pree, -1, sizeof(pree));
    for (int i = s; i <= t; i++)	dis[i] = INF;
    dis[s] = 0, que.push(s), inque[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inque[u] = false;
        for (int i = pre[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && dis[u]+w < dis[v]) {
                dis[v] = dis[u]+w, pree[v] = i;
                if (!inque[v])	que.push(v), inque[v] = true;
            }
        }
    }
    if (dis[t] == INF)	return false;
    int flow = INF;
    for (int i = pree[t]; ~i; i = pree[E[i^1].v])	flow = min(flow, E[i].c);
    for (int i = pree[t]; ~i; i = pree[E[i^1].v])	E[i].c -= flow, E[i^1].c += flow;
    ans += dis[t];	return true;
}
int main() {
    scanf("%d%d", &m, &n), init();
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)	insert(s, i, 1, 0);
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	for (int k = 1; k <= n; k++)	insert(i, j*n+k, 1, a[i][j]*k);
    for (int j = 1; j <= m; j++)	for (int k = 1; k <= n; k++)	insert(j*n+k, t, 1, 0);
    while (SPFA()) ;
    printf("%.2lf", (double)ans/n);
    return 0;
}